#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2022/5/12 17:37
# @Author  : Yizheng Dai
# @Email   : 387942239@qq.com
# @File    : _90_subsetsWithDup.py
from copy import deepcopy


class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        path = []
        res = []
        nums = sorted(nums)
        def dfs(index):
            path.append(deepcopy(path))
            for i in range(index, len(nums)):
                if i>index and nums[i]==nums[i-1]:continue
                path.append(nums[i])
                dfs(i+1)
                path.pop()
        dfs(0)
        return res
